/*
 * @Author: your name
 * @Date: 2024-06-21 10:31:22
 * @LastEditTime: 2024-06-21 10:34:02
 * @LastEditors: your name
 * @Description: In User Settings Edit
 * @FilePath: \.leetcode\96.不同的二叉搜索树.cpp
 */
/*
 * @lc app=leetcode.cn id=96 lang=cpp
 *
 * [96] 不同的二叉搜索树
 */

// @lc code=start
class Solution {
public:
    int numTrees(int n) {
        vector<int> dp(n+1);
        dp[0] =1;
        for(int i = 1; i <=n; i++){
            for(int j = 1; j <= i; j++){
                dp[i] += dp[j-1] * dp[i-j];
            }
        }
        return dp[n];
    }
};
// @lc code=end

